# -*- coding: utf-8 -*-
# @Date    : 2017-10-18
# @Author  : fancy.yuan

stations = {
    'kone': set(['id', 'nv', 'ut']),
    'ktwo': set(['wa', 'id', 'mt']),
    'kthree': set(['or', 'nv', 'ca']),
    'kfour': set(['nv', 'ut']),
    'kfive': set(['ca', 'az'])
}

def greedy():
    selected_stations = []
    states_needed = set(['mt', 'wa', 'or', 'id', 'nv', 'ut'])
    elected_states = set([])

    while elected_states.intersection(states_needed) != states_needed:
        m_stat, m_length = None, 0
        cur_need_states = states_needed - elected_states
        for station in stations:
            # import pdb; pdb.set_trace()
            if station not in selected_stations:
                length = len(cur_need_states.intersection(stations[station]))
                if length > m_length:
                    print station
                    m_stat, m_length = station, length
        selected_stations.append(m_stat)
        elected_states = elected_states.union(stations[m_stat])
        print elected_states

    print selected_stations

if __name__ == '__main__':
    greedy()
